package LeetCode;
//编写一个函数，检查输入的链表是否是回文的。
public class TesrInterview02_06 {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, low = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            low = low.next;
        }
        ListNode newHead = reverseList(low);
        while (newHead != null) {
            if (newHead.val != head.val) {
                return false;
            }
            newHead = newHead.next;
            head = head.next;
        }
        return true;
    }

    public ListNode reverseList(ListNode head) {
        //递归
        if (head == null || head.next == null) {
            return head;
        }
        ListNode sec = head.next;
        ListNode newHead = reverseList(sec);
        sec.next = head;
        head.next = null;
        return newHead;
        //头插法
//        if (head == null || head.next == null) {
//            return head;
//        } else {
//            ListNode dummyHead = new ListNode(-10);
//            while (head != null) {
//                ListNode node = new ListNode(head.val);
//                node.next = dummyHead.next;
//                dummyHead.next = node;
//                head = head.next;
//            }
//        return dummyHead.next;
//    }
        //原地移动
//        if (head == null || head.next == null) {
//            return head;
//        }
//        ListNode prev = null;
//        ListNode cur = head;
//        while (cur != null) {
//            ListNode next = cur.next;
//            cur.next = prev;
//            prev = cur;
//            cur = next;
//        }
//        return prev;
    }
}
